package demo2;

import java.util.*;

public class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > target){
                right--;
            }else if(nums[mid] < target){
                left++;
            }else{
                return mid;
            }
        }
        return -1;
    }

    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;
        if(nums.length == 0) { return ret;}

        int left = 0, right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        if(nums[left] != target) { return ret;}
        ret[0] = left;

        left = 0;
        right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid;
            }
        }
        ret[1] = left;
        return ret;
    }

//    public static int mySqrt(int x) {
//        if(x < 1) { return 0;}
//        long left = 1, right = x;
//        while(left < right){
//            long mid = left + (right - left) / 2;
//            if(mid * mid < x){
//                left = mid + 1;
//            }else{
//                right = mid;
//            }
//        }
//        return (int)left;
//    }

    public static int mySqrt(int x) {
        if(x < 1) { return 0;}
        long left = 1, right = x;
        while(left < right){
            long mid = left + (right - left + 1) / 2;
            if(mid * mid > x){
                right = mid - 1;
            }else{
                left = mid;
            }
        }
        return (int)left;
    }

    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return nums[left] < target ? left + 1 : left;
    }


    public static void main(String[] args) {
        System.out.println(mySqrt(8));
    }
}
